Lưu Vĩnh Phúc vừa đi vừa tuyển thêm quân từ các toán thổ phỉ khác mà không bị ai chặn lại hay ngăn trở gì. Đến gần Sơn Tây, quân Cờ đen khi đó đã lên tới 500 người dừng lại lập doanh trại. Sự hiện diện của một đội quân vũ trang trong lãnh thổ của các bộ tộc Mông miền núi là một sự đe dọa với họ, nên xung đột vũ trang đã nổ ra. Quân Cờ đen phục kích và đánh bại cuộc tấn công của thổ dân, đồng thời giết chết một thủ lĩnh của họ[1]. Viên thủ lĩnh này chống đối chính quyền nhà Nguyễn, nên nhân cơ hội đó nhà Nguyễn chính thức ban cho Lưu Vĩnh Phúc chức vị Cửu phẩm bách hộ để tiếp tục công việc bình định vùng này.

Tuy vậy, đánh nhau với người thiểu số không phải là mối quan tâm chính của Lưu Vĩnh Phúc, nên năm 1868, Lưu Vĩnh Phúc quay ra tranh giành khu vực thị trấn Lào Cai, tức châu Bảo Thắng, một món mồi béo bở, lúc bấy giờ đang nằm dưới sự kiểm soát của các thương gia có vũ trang người Quảng Đông. Quân Cờ đen tự tiện thu thuế, khai khoáng, cướp bóc khắp nơi, quan quân nhà Nguyễn cũng không ngăn cản được.

Nhận được tin về những thắng lợi dễ dàng của Lưu Vĩnh Phúc, những toán quân còn lại của Ngô Vương, lúc này đang bị quân Thanh dồn ép về gần biên giới, theo Hoàng Sùng Anh (Huang Ch'ung-ying, cháu Ngô Vương) lập thành quân Cờ vàng, tràn qua biên giới chiếm thị trấn Hà Giang nằm trên bờ sông Lô. Quân Cờ vàng được tổ chức theo mô hình quân Cờ đen, nhưng với số lượng đông hơn gấp hai, ba lần. Tuy nhiên Hà Giang không phải là một nơi có thể đem lại nhiều lợi nhuận như Lào Cai, nên xung đột giành quyền lợi giữa hai nhóm Cờ đen và Cờ vàng bùng nổ.

Năm 1869, quân Cờ đen phục kích đánh tan tác quân Cờ vàng tại Lào Cai, rồi truy quét Cờ vàng đến tận hang ổ tại Hà Giang. Phối hợp với quân Cờ đen là quân nhà Nguyễn và quân Thanh của tướng Phùng Tử Tài, quân Cờ vàng phải tháo chạy khỏi căn cứ Hà Giang. Tuy nhiên, do dịch bệnh và khí hậu khắc nghiệt nên quân Thanh phải rút về, quân Cờ vàng tiếp tục kiểm soát một vùng rộng lớn ở khoảng giữa sông Hồng đến biên giới, từ Lào Cai đến Sơn Tây. Đến năm 1875, quân Cờ đen mở chiến dịch quyết định đánh chiếm Hà Giang, phối hợp với họ không những là quân nhà Nguyễn mà cả quân Thanh từ Quảng Tây và Vân Nam. Hoàng Sùng Anh bị truy đuổi, bị bộ hạ làm phản, bị bắt rồi bị giết chết.

Do chiến thắng quân Cờ vàng mà quân Cờ đen của Lưu Vĩnh Phúc chính thức được chính quyền nhà Thanh bảo trợ, ngược lại Lưu Vĩnh Phúc cũng xóa bỏ mặc cảm khi trước, hạ lệnh cho thủ hạ dóc tóc kiểu Mãn Châu để tỏ lòng trung thành với nhà Thanh. Về phần nhà Nguyễn, mặc dù sử dụng Lưu Vĩnh Phúc nhưng triều đình Huế vẫn còn nghi ngờ về lòng trung thành của Lưu và quân Cờ đen. Vì vậy, năm 1873, Hoàng Tá Viêm xin phong cho Lưu chức Phòng ngự sứ nhưng vua Tự Đức không đồng ý.